#include <limits.h>
// #include <limits>
#include <queue>
#include <iostream>
#include <algorithm>

// dijkstra(迪杰斯特拉)算法求解单源最短路径
// Ref: https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.999.0.0
typedef std::pair<int, int> pii;                // (节点, 权重)
typedef std::vector<std::vector<pii>> AdjList;  // AdjList邻接表;

typedef std::vector<std::vector<int>> AdjMat;   //  邻接矩阵

//TODO: 邻接矩阵完成
AdjMat mat = {{0, 4, INT_MAX, INT_MAX,INT_MAX,INT_MAX,INT_MAX, 8, INT_MAX},  //! node 0 -> others
            {4, 0, 8, INT_MAX,INT_MAX,INT_MAX,INT_MAX, 11, INT_MAX},         //! node 1 -> others
            {INT_MAX, 8, 0, 7,INT_MAX,INT_MAX,INT_MAX, INT_MAX, 2},          //! node 2 -> others
            {INT_MAX, INT_MAX, 7, 0, 9, 14,INT_MAX, INT_MAX, INT_MAX},       //! node 3 -> others
            {INT_MAX, INT_MAX, INT_MAX, 9, 0, 10,INT_MAX, INT_MAX, INT_MAX}, //! node 4 -> others
            {INT_MAX, INT_MAX, 4, 14, 10, 0, 2, INT_MAX, INT_MAX},           //! node 5 -> others
            {INT_MAX, INT_MAX, INT_MAX, INT_MAX,INT_MAX,2, 0, 1, 6},         //! node 6 -> others
            {8, 11, INT_MAX, INT_MAX,INT_MAX,INT_MAX, 1, 0, 7},              //! node 7 -> others
            {INT_MAX, 2, INT_MAX, INT_MAX,INT_MAX,INT_MAX,6, 7, 0}           //! node 8 -> others
            };
 

AdjList edges = {{{1,4}, {7,8}},              // node0
                {{2,8}, {7,11}},              // node1
                {{1,8},{3,7},{8,2}},          // node2
                {{2,7},{4,9},{5,14}},         // node3
                {{3,9},{5,10}},               // node4
                {{6,2},{2,4},{3,14},{4,10}},  // node5
                {{7,1},{8,6},{5,2}},          // node6
                {{0,8},{1,11},{8,7},{6,1}},   // node7
                {{2,2},{7,7},{6,6}},          // node8
                };

/**
 * @brief 基于邻接矩阵表示的图的迪杰斯特拉单源最短路径算法
 * 
 * @param  edges 
 * @param  src 
 * @param  dst 
 * @param  path 
 * @return int 
 */
int dijkstra(AdjList& edges, int src, int dst, std::vector<int>& path) {
    int n = edges.size();                       //! 图中有多少个顶点(节点的总数)
    // std::vector<int>    dist(n, INT_MAX);    // src节点到其它节点最近的距离
    std::vector<int>    dist(n, INT_MAX);       // src节点到其它节点最近的距离
    std::vector<int>    prev(n, -1);            // 路径中每个节点的前一个编号节点

    //! 优先队列，默认是最大堆(堆顶存放最大的元素)，这里我们改成最小堆
    //! 注意: 每个pii存储的数据格式为<src->dst距离, 节点编号>
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
    // std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;

    dist[src] = 0;                              // 将到自己的距离标记为0
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;                //! 堆中距离src最近的点
        pq.pop();

        if (u == dst) break;                    //! 已经标记到目标节点dst，直接退出

        //! 依次遍历当前节点u的邻居节点 
        for (const auto& neighbor : edges[u]) {
            int v = neighbor.first;             // first是邻居节点编号
            int weight = neighbor.second;       // second是到邻居节点的距离
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    path.clear();
    int current = dst;
    // while (current != -1) {
    //     path.push_back(current);
    //     current = prev[current];
    // }
    while (true) {
        path.push_back(current);
        current = prev[current];
        if (current == src)
            break;
    }

    std::reverse(path.begin(), path.end());
    return 0;
}

////////////////////////////////////////////////////////////////////
// Dijkstra算法的步骤：
//
//  1. 使用一个顶点大小的向量数组记录src顶点到所有顶点的距离： 
//       - 如果src顶点到目标点有直连，则距离记录相应的值;
//       - 如果src顶点与目标节点不直连，则距离设为正无穷，我们通常表示为INT_MAX;
//       - 节点自己到自己的距离为0;
//       - 使用一个乡村最优路径:  std::map<int, bool> = {{0, false}, ...}
//       - 本例中记录为: dists    = {0,INX_MAX,INX_MAX,INT_MAX,INT_MAX,INT_MAX,INT_MAX,INX_MAX,INT_MAX}
//
//  2. 为了记录最短路径，我们需要用一个数据来保存每个节点的前面节点
//       - 本例中记录为: pre_node = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
//
//
//  3. 开始进行算法，重复如下步骤：
//       step-1 在当前dists中寻找src到所有目标的最小值，将其标记为最短路径中的点, 首次为节点0, path[0] = true;
//       step-2 接着更新选中的节点0到其邻居的距离，分别为0—>1:4, 0->7:8, 此时更新dist和pre_node为：
//              dists    = {0, 4, INX_MAX,INT_MAX,INT_MAX,INT_MAX,INT_MAX,8,INT_MAX}
//              pre_node = {-1, 0, -1, -1, -1, -1, -1, 0, -1};
// 
//
//       step-1 在当前dists中寻找src到所有目标的最小值，将其标记为最短路径中的点, 本次为节点1(到0的距离为4), path[1]=1;
//       step-2 接着更新选中的节点1到其邻居的距离，分别为1—>2:8, 1->7:11, 此时更新dist和pre_node为：
//              假设经过节点1和2， 0->2的距离变为4+8=12，  目前0->2的距离为INT_MAX, 所以替换;
//              假设经过节点1和7， 0->7的距离变为4+11=15， 目前0->2的距离为8, 所以不替换;
//              dists    = {0, 4, 12, INT_MAX,INT_MAX,INT_MAX,INT_MAX,8,INT_MAX}
//              pre_node = {-1, 0, 1, -1, -1, -1, -1, 0, -1};
//
//       step-1 在当前dists中寻找src到所有目标的最小值，将其标记为最短路径中的点, 本次为节点7(到0的距离为8), path[2]=7;
//       step-2 接着更新选中的节点1到其邻居的距离，分别为7—>8:7, 7->6:1, 此时更新dist和pre_node为：
//              假设经过节点7和8， 0->8的距离变为8+7=15，目前0->8的距离为INT_MAX, 所以替换;
//              假设经过节点7和6， 0->6的距离变为8+1=9， 目前0->6的距离为INT_MAX, 所以替换;
//              dists    = {0, 4, 12, INT_MAX,INT_MAX,INT_MAX,9,8,15}
//              pre_node = {-1, 0, 1, -1, -1, -1, 7, 0, 7};
//
//   4. 循环终止条件： 目标节点4被标记，然后根据节点4的pre_node依次向前反推路径即可


//  g++ dijkstra.cpp -o main -std=c++11 
int main(int argc, char* argv[]) {
    int src = 0, dst = 4;
    std::vector<int> path;

    dijkstra(edges, src, dst, path);
    
    if (path.empty()) {
        std::cout << "No path found from " << src << " to " << dst <<  std::endl;
    } else {
         std::cout << "Shortest path from " << src << " to " << dst << ": ";
        for (int node : path) {
             std::cout << node << " ";
        }
         std::cout <<  std::endl;
    }

    return 0;
}